#include<bits/stdc++.h>
using namespace std;
#define gc getchar
#define pc putchar
#define pb push_back
#define mp make_pair
#define ls (id<<1)
#define rs ((id<<1)|1)
#define mid ((l+r)>>1)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)

int read(){
    int ret=0,f=0; char ch=gc();
    while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gc();
    while(ch>='0'&&ch<='9') ret=(ret<<1)+(ret<<3)+(ch^48),ch=gc();
    return f?-ret:ret;
}

void write(int x){
    if(!x) return pc('0'),void();
    if(x<0) pc('-'),x=-x;
    int stk[30],tp=0;
    while(x) stk[++tp]=x%10,x/=10;
    while(tp) pc('0'+stk[tp--]);
    return;
}

const int Maxn=1e5+10,Mod=1e9+7;
int N,T;
string f1,f2,S,G;

int main(){
    freopen("brotherhood.in","r",stdin);
    freopen("brotherhood.out","w",stdout);
    N=read(),T=read();
    f1="0",f2="1";
    For(i,3,N) S=f2+f1,f1=f2,f2=S;
    For(i,1,T){
        cin>>G; int l1=S.size(),l2=G.size(),sol=0;
        For(k,0,l1-l2){
            bool f=0;
            For(p,0,l2-1) if(S[k+p]!=G[p]){f=1; break;}
            if(!f) ++sol;
        }
        write(sol%Mod),pc('\n');
    }
    return 0;
}
